{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Score After N Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math #dynamic-programming #backtracking #bitmask #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学 #动态规划 #回溯 #状态压缩 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 次操作后的最大分数和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你 <code>nums</code> ，它是一个大小为 <code>2 * n</code> 的正整数数组。你必须对这个数组执行 <code>n</code> 次操作。</p>\n",
    "\n",
    "<p>在第 <code>i</code> 次操作时（操作编号从 <strong>1</strong> 开始），你需要：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择两个元素 <code>x</code> 和 <code>y</code> 。</li>\n",
    "\t<li>获得分数 <code>i * gcd(x, y)</code> 。</li>\n",
    "\t<li>将 <code>x</code> 和 <code>y</code> 从 <code>nums</code> 中删除。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回 <code>n</code> 次操作后你能获得的分数和最大为多少。</p>\n",
    "\n",
    "<p>函数 <code>gcd(x, y)</code> 是 <code>x</code> 和 <code>y</code> 的最大公约数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>最优操作是：\n",
    "(1 * gcd(1, 2)) = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,4,6,8]\n",
    "<b>输出：</b>11\n",
    "<b>解释：</b>最优操作是：\n",
    "(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,3,4,5,6]\n",
    "<b>输出：</b>14\n",
    "<b>解释：</b>最优操作是：\n",
    "(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 7</code></li>\n",
    "\t<li><code>nums.length == 2 * n</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-score-after-n-operations](https://leetcode.cn/problems/maximize-score-after-n-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-score-after-n-operations](https://leetcode.cn/problems/maximize-score-after-n-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]', '[3,4,6,8]', '[1,2,3,4,5,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        half = n // 2\n",
    "        gd = [[0] * n for _ in range(n)]\n",
    "        def gcd(x, y):\n",
    "\n",
    "            if y > x:\n",
    "                x, y = y, x\n",
    "\n",
    "            while x % y != 0:\n",
    "                x, y = y, x % y\n",
    "            return y\n",
    "\n",
    "        had = []    \n",
    "        used = [0] * n\n",
    "        ans = 0\n",
    "        def dfs(i):\n",
    "            \n",
    "            if len(had) == half:\n",
    "                sortedHad = sorted(had)\n",
    "                nonlocal ans\n",
    "                ans = max(ans, sum(i * x for i, x in enumerate(sortedHad, 1)))\n",
    "                return \n",
    "\n",
    "            while i < n and used[i]:\n",
    "                i += 1\n",
    "\n",
    "\n",
    "            used[i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if used[j]:\n",
    "                    continue\n",
    "                used[j] = 1\n",
    "                had.append(gcd(nums[i], nums[j]))\n",
    "                dfs(i+1)\n",
    "                had.pop()\n",
    "                used[j] = 0\n",
    "            used[i] = 0\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        half = n // 2\n",
    "        gd = [[0] * n for _ in range(n)]\n",
    "        \n",
    "        def gcd(x, y):\n",
    "\n",
    "            if y > x:\n",
    "                x, y = y, x\n",
    "\n",
    "            while x % y != 0:\n",
    "                x, y = y, x % y\n",
    "            return y\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                gd[i][j] = gcd(nums[i], nums[j])\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        had = []    \n",
    "        used = [0] * n\n",
    "        ans = 0\n",
    "        def dfs(i):\n",
    "            \n",
    "            if len(had) == half:\n",
    "                sortedHad = sorted(had)\n",
    "                nonlocal ans\n",
    "                ans = max(ans, sum(i * x for i, x in enumerate(sortedHad, 1)))\n",
    "                return \n",
    "\n",
    "            while i < n and used[i]:\n",
    "                i += 1\n",
    "\n",
    "\n",
    "            used[i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if used[j]:\n",
    "                    continue\n",
    "                used[j] = 1\n",
    "                had.append(gd[i][j])\n",
    "                dfs(i+1)\n",
    "                had.pop()\n",
    "                used[j] = 0\n",
    "            used[i] = 0\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        n = len(nums)\n",
    "        half = n // 2\n",
    "        gd = [[0] * n for _ in range(n)]\n",
    "\n",
    "        def gcd(x, y):\n",
    "\n",
    "            while x % y != 0:\n",
    "                x, y = y, x % y\n",
    "            return y\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                gd[i][j] = gcd(nums[i], nums[j])\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        had = []    \n",
    "        used = [0] * n\n",
    "        ans = 0\n",
    "        def dfs(i):\n",
    "            \n",
    "            if len(had) == half:\n",
    "                sortedHad = sorted(had)\n",
    "                nonlocal ans\n",
    "                ans = max(ans, sum(i * x for i, x in enumerate(sortedHad, 1)))\n",
    "                return \n",
    "\n",
    "            while i < n and used[i]:\n",
    "                i += 1\n",
    "\n",
    "\n",
    "            used[i] = 1\n",
    "            for j in range(i+1, n):\n",
    "                if used[j]:\n",
    "                    continue\n",
    "                used[j] = 1\n",
    "                had.append(gd[i][j])\n",
    "                dfs(i+1)\n",
    "                had.pop()\n",
    "                used[j] = 0\n",
    "            used[i] = 0\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                g[i][j] = gcd(nums[i], nums[j])\n",
    "        f = [0] * (1 << m)\n",
    "        for k in range(1 << m):\n",
    "            if (cnt := k.bit_count()) % 2 == 0:\n",
    "                for i in range(m):\n",
    "                    if k >> i & 1:\n",
    "                        for j in range(i + 1, m):\n",
    "                            if k >> j & 1:\n",
    "                                f[k] = max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j])\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        dp = [0] * (m := (1 << (n := len(nums))))\n",
    "        for mask in range(1, m):\n",
    "            if (k := bin(mask).count('1')) & 1:\n",
    "                continue\n",
    "            for i in range(n):\n",
    "                if not ((1 << i) & mask):\n",
    "                    continue\n",
    "                for j in range(i + 1, n):\n",
    "                    if not ((1 << j) & mask):\n",
    "                        continue\n",
    "                    dp[mask] = max(dp[mask], dp[mask ^ (1 << i) ^ (1 << j)] + (k >> 1) * gcd(nums[i], nums[j]))\n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)//2\n",
    "        FULL = (1<<(2*n))-1\n",
    "        f = [0]*(FULL+1)\n",
    "        f[0] = 0\n",
    "        # 0表示不可选，1表示可选\n",
    "        for s in range(1,FULL+1):\n",
    "            one_num = bin(s).count('1')\n",
    "            if one_num%2==1:\n",
    "                continue\n",
    "            oper_idx = n - (one_num//2) + 1\n",
    "            one_pos = [-1]*one_num\n",
    "            idx = 0\n",
    "            for i in range(2*n):\n",
    "                if (s>>i)&1:\n",
    "                    one_pos[idx] = i\n",
    "                    idx+=1\n",
    "\n",
    "            for x,y in combinations(one_pos, 2):\n",
    "                prev = s ^ (1<<x) ^ (1<<y)\n",
    "                f[s] = max(f[s], oper_idx*math.gcd(nums[n-x-1], nums[n-y-1])+f[prev])\n",
    "\n",
    "            pass\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=1<<n\n",
    "        dp=[0]*m   #状态1表示未删除,0表示已删除\n",
    "        check=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                check[i][j]=gcd(nums[i],nums[j])\n",
    "        #预处理完成\n",
    "        for mask in range(1,m):\n",
    "            op=mask.bit_count()\n",
    "            if op&1: continue\n",
    "            for i in range(n):\n",
    "                if mask>>i&1:\n",
    "                    for j in range(i+1,n):\n",
    "                        if mask>>j&1:\n",
    "                            dp[mask]=max(dp[mask],dp[mask^(1<<i)^(1<<j)]+check[i][j]*(op//2))\n",
    "        return dp[m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        gcds = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                gcds[i][j] = gcd(nums[i], nums[j])\n",
    "        for i in range(1 << n):\n",
    "            if (cnt:= i.bit_count()) & 1: continue\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    for k in range(j+1, n):\n",
    "                        if i >> k & 1:\n",
    "                            f[i] = max(f[i], f[i ^ (1 << j) ^ (1 << k)] + cnt // 2 * gcds[j][k])\n",
    "        return f[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0] * (1 << n)\n",
    "\n",
    "        for mask in range(1, 1 << n):\n",
    "            cnt = mask.bit_count()\n",
    "            if cnt % 2:\n",
    "                continue\n",
    "            for i in range(n):\n",
    "                if mask >> i & 1:\n",
    "                    for j in range(i + 1, n):\n",
    "                        if mask >> j & 1:\n",
    "                            dp[mask] = max(dp[mask], dp[mask ^ (1 << i | 1 << j)] + gcd(nums[i], nums[j]) * cnt // 2)\n",
    "        return dp[mask]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, a: List[int]) -> int:\n",
    "        n=len(a)\n",
    "        f=[0]*(1<<n)\n",
    "        for s in range(1<<n):\n",
    "            if s.bit_count()%2==1:\n",
    "                continue\n",
    "            for i in range(n):\n",
    "                if s>>i&1:\n",
    "                    continue\n",
    "                for j in range(n):\n",
    "                    if i==j or s>>j&1==1:\n",
    "                        continue\n",
    "                    ns=s|(1<<i)|(1<<j)\n",
    "                    f[ns]=max(f[ns],f[s]+gcd(a[i],a[j])*(ns.bit_count()//2))\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from itertools import combinations\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)//2\n",
    "        FULL = (1<<(2*n))-1\n",
    "        f = [0]*(FULL+1)\n",
    "        f[0] = 0\n",
    "        # f[s]表示在可选状态为s情况下的最大得分之和\n",
    "        # 0表示不可选，1表示可选\n",
    "        # 初始 s=0，表示全部不可选，得分为0。每次遇到1的个数为奇数时跳过\n",
    "        # 每个状态枚举所有选择两个 1 的情况并进行状态转移\n",
    "        for s in range(1,FULL+1):\n",
    "            one_num = bin(s).count('1')\n",
    "            if one_num%2==1:\n",
    "                continue\n",
    "            oper_idx = n - (one_num//2) + 1\n",
    "            one_pos = [-1]*one_num\n",
    "            idx = 0\n",
    "            for i in range(2*n):\n",
    "                if (s>>i)&1:\n",
    "                    one_pos[idx] = i\n",
    "                    idx+=1\n",
    "\n",
    "            for x,y in combinations(one_pos, 2):\n",
    "                prev = s - (1<<x) - (1<<y)\n",
    "                f[s] = max(f[s], oper_idx*math.gcd(nums[n-x-1], nums[n-y-1])+f[prev])\n",
    "\n",
    "            pass\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                g[i][j] = gcd(nums[i], nums[j])\n",
    "        f = [0] * (1 << m)\n",
    "        for k in range(1 << m):\n",
    "            if (cnt := k.bit_count()) % 2 == 0:\n",
    "                for i in range(m):\n",
    "                    if k >> i & 1:\n",
    "                        for j in range(i + 1, m):\n",
    "                            if k >> j & 1:\n",
    "                                f[k] = max(f[k], f[k ^ (1 << i) ^ (\n",
    "                                    1 << j)] + cnt // 2 * g[i][j])\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=1<<n\n",
    "        dp=[0]*m   #状态1表示未删除,0表示已删除\n",
    "        #预处理完成\n",
    "        for mask in range(1,m):\n",
    "            op=mask.bit_count()\n",
    "            if op&1: continue\n",
    "            for i in range(n):\n",
    "                if mask>>i&1:\n",
    "                    for j in range(i+1,n):\n",
    "                        if mask>>j&1:\n",
    "                            dp[mask]=max(dp[mask],dp[mask^(1<<i)^(1<<j)]+gcd(nums[i],nums[j])*(op//2))\n",
    "        return dp[m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        m=1<<n\n",
    "        dp=[0]*m   #状态1表示未删除,0表示已删除\n",
    "        check=[[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                check[i][j]=gcd(nums[i],nums[j])\n",
    "        #预处理完成\n",
    "        #其实是压缩了一维,把操作次数压缩到二进制数中了,就是可以通过状态mask求出操作次数\n",
    "        for mask in range(1,m):\n",
    "            op=mask.bit_count()\n",
    "            if op&1: continue\n",
    "            for i in range(n):\n",
    "                if mask>>i&1:\n",
    "                    for j in range(i+1,n):\n",
    "                        if mask>>j&1:\n",
    "                            dp[mask]=max(dp[mask],dp[mask^(1<<i)^(1<<j)]+check[i][j]*(op//2))\n",
    "        return dp[m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        #最多14个数字，摆明了是让状态压缩\n",
    "        n = len(nums)\n",
    "        #---- 预计算一下gcd数组，虽然只有14个数字，但是数字都很大\n",
    "        g = [[0]*n  for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                g[i][j] =  self.self_gcd(nums[i],nums[j])\n",
    "        w=1 << n\n",
    "        dp = [0]*w\n",
    "        for s in range(3, w):\n",
    "            cnt1 = bin(s).count('1')\n",
    "            t,yu = divmod(cnt1, 2)\n",
    "            if not yu:\n",
    "                for i in range(n-1):\n",
    "                    for j in range(i+1, n):\n",
    "                        x,y=1<<i,1<<j\n",
    "                        if s&x and s&y:\n",
    "                            if (m:= (dp[s-x-y] + t*g[i][j]))>dp[s]:dp[s]=m\n",
    "        return dp[-1]\n",
    "\n",
    "    def self_gcd(self,a,b):\n",
    "        while b:\n",
    "            t=a%b\n",
    "            a,b=b,t\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        gcds = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):  # 预计算 gcd，不放入DP循环中\n",
    "            for j in range(i+1, n):\n",
    "                gcds[i][j] = gcd(nums[i], nums[j])\n",
    "\n",
    "        for i in range(1 << n):\n",
    "            if (cnt:= i.bit_count()) & 1: continue  # 非法状态，不计算\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    for k in range(j+1, n): # 找到2个1\n",
    "                        if i >> k & 1:\n",
    "                            f[i] = max(f[i], f[i ^ (1 << j) ^ (1 << k)] + (n - cnt + 2) // 2 * gcds[j][k])\n",
    "        return f[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        gcds = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                gcds[i][j] = gcd(nums[i], nums[j])\n",
    "        for i in range(1 << n):\n",
    "            if (cnt:= i.bit_count()) & 1: continue\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    for k in range(j+1, n):\n",
    "                        if i >> k & 1:\n",
    "                            f[i] = max(f[i], f[i ^ (1 << j) ^ (1 << k)] + cnt // 2 * gcd(nums[j], nums[k]))\n",
    "        return f[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        def bit_ones(x) :\n",
    "            count = 0\n",
    "            while x > 0 :\n",
    "                count += 1\n",
    "                x &= (x-1)\n",
    "            return count\n",
    "\n",
    "\n",
    "        N = len(nums)\n",
    "\n",
    "        dp = [ [0] * N for _ in range(N)]\n",
    "\n",
    "        for i in range(N) :\n",
    "            for j in range(i+1,N) :\n",
    "                dp[i][j] = gcd(nums[i], nums[j])\n",
    "\n",
    "        status = [0] * (1 << N)\n",
    "\n",
    "        for kk in range(1 << N) :\n",
    "            bit_ones_count = bit_ones(kk)\n",
    "\n",
    "            if bit_ones_count % 2  != 0 :\n",
    "                continue\n",
    "\n",
    "            for i in range(N) : \n",
    "                if kk >> i & 1 :\n",
    "                    for j in range(i+1, N) :\n",
    "                        if kk >> j & 1:\n",
    "                            status[kk] = max(status[kk], dp[i][j] * bit_ones_count / 2 + status[kk ^ (1 << i) ^ (1 << j)])\n",
    "\n",
    "        return int(status[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * (1 << n)\n",
    "        gcds = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                gcds[i][j] = gcd(nums[i], nums[j])\n",
    "        for i in range(1 << n):\n",
    "            if (cnt:= i.bit_count()) & 1: continue\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    for k in range(j+1, n):\n",
    "                        if i >> k & 1:\n",
    "                            f[i] = max(f[i], f[i ^ (1 << j) ^ (1 << k)] + cnt // 2 * gcds[j][k])\n",
    "        return f[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                g[i][j] = gcd(nums[i], nums[j])\n",
    "        f = [0] * (1 << m)\n",
    "        for k in range(1 << m):\n",
    "            if (cnt := k.bit_count()) % 2 == 0:\n",
    "                for i in range(m):\n",
    "                    if k >> i & 1:\n",
    "                        for j in range(i + 1, m):\n",
    "                            if k >> j & 1:\n",
    "                                f[k] = max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j])\n",
    "        return f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                g[i][j] = gcd(nums[i], nums[j])\n",
    "        f = [0] * (1 << m)\n",
    "        for k in range(1 << m):\n",
    "            if (cnt := k.bit_count()) % 2 == 0:\n",
    "                for i in range(m):\n",
    "                    if k >> i & 1:\n",
    "                        for j in range(i + 1, m):\n",
    "                            if k >> j & 1:\n",
    "                                f[k] = max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j])\n",
    "        return f[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, a: List[int]) -> int:\n",
    "        n=len(a)\n",
    "        f=[0]*(1<<n)\n",
    "        for s in range(1<<n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i!=j and s>>i&1==0 and s>>j&1==0:\n",
    "                        ns=s|(1<<i)|(1<<j)\n",
    "                        f[ns]=max(f[ns],f[s]+gcd(a[i],a[j])*(ns.bit_count()//2))\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        g = [[0] * m for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                g[i][j] = gcd(nums[i], nums[j])\n",
    "        f = [0] * (1 << m)\n",
    "        for k in range(1 << m):\n",
    "            if (cnt := k.bit_count()) % 2 == 0:\n",
    "                for i in range(m):\n",
    "                    if k >> i & 1:\n",
    "                        for j in range(i + 1, m):\n",
    "                            if k >> j & 1:\n",
    "                                f[k] = max(f[k], f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j])\n",
    "        return f[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        m = len(nums)\n",
    "        n = m // 2\n",
    "        \n",
    "        f = [[0] * (1 << m) for _ in range(n + 1)]\n",
    "        \n",
    "        for mask in range(1 << m):\n",
    "            count = mask.bit_count()\n",
    "            if count % 2 != 0:\n",
    "                continue\n",
    "                \n",
    "            idx = count // 2 + 1\n",
    "            \n",
    "            for i in range(m):\n",
    "                for j in range(i + 1, m):\n",
    "                    if (mask >> i) & 1 == 0 and (mask >> j) & 1 == 0:\n",
    "                        f[idx][mask | (1 << i) | (1 << j)] = max(\n",
    "                            f[idx][mask | (1 << i) | (1 << j)],\n",
    "                            f[idx - 1][mask] + gcd(nums[i], nums[j]) * idx\n",
    "                        )\n",
    "        \n",
    "        return f[n][(1 << m) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        G = [[0] * n for _ in range(n)]\n",
    "        memo = [-1] * (2 ** n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                G[i][j] = gcd(nums[i], nums[j])\n",
    "        def dfs(mask):\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            if memo[mask] != -1: return memo[mask]\n",
    "            res, c = -inf, (n - mask.bit_count()) // 2 + 1\n",
    "            for i in range(n):\n",
    "                if not mask >> i & 1: continue\n",
    "                for j in range(n):\n",
    "                    if i == j: continue\n",
    "                    if mask >> j & 1:\n",
    "                        res = max(res, dfs(mask ^ (1 << i) ^ (1 << j)) + c * G[i][j])\n",
    "            memo[mask] = res\n",
    "            return res\n",
    "        return dfs((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        G = [[0] * n for _ in range(n)]\n",
    "        memo = [-1] * (2 ** n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                G[i][j] = gcd(nums[i], nums[j])\n",
    "        def dfs(mask):\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            if memo[mask] != -1: return memo[mask]\n",
    "            res, c = -inf, (n - mask.bit_count()) // 2 + 1\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i == j: continue\n",
    "                    if mask >> i & 1 and mask >> j & 1:\n",
    "                        res = max(res, dfs(mask ^ (1 << i) ^ (1 << j)) + c * G[i][j])\n",
    "            memo[mask] = res\n",
    "            return res\n",
    "        return dfs((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        G = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                G[i][j] = gcd(nums[i], nums[j])\n",
    "        @cache\n",
    "        def dfs(mask):\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            res, c = -inf, (n - mask.bit_count()) // 2 + 1\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i == j: continue\n",
    "                    if mask >> i & 1 and mask >> j & 1:\n",
    "                        res = max(res, dfs(mask ^ (1 << i) ^ (1 << j)) + c * G[i][j])\n",
    "            return res\n",
    "        return dfs((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        L = len(nums)\n",
    "        N = L // 2\n",
    "        # i: 第i次操作(从1开始)\n",
    "        # state: nums中元素的使用情况\n",
    "        @cache\n",
    "        def dfs(i, state):\n",
    "            if i > N: return 0\n",
    "            # 先获取nums目前可用的元素(下标)\n",
    "            usable = [j for j in range(L) if state >> j & 1 == 0]\n",
    "            # 从中任取两个，枚举所有的选取方案，从中取最大值即可\n",
    "            # combinations函数详解见官方文档\n",
    "            # https://docs.python.org/zh-cn/3/library/itertools.html?highlight=itertool#itertools.combinations\n",
    "            return max(i * gcd(nums[a], nums[b]) + dfs(i + 1, state | (1 << a) | (1 << b)) for a, b in combinations(usable, 2))\n",
    "        \n",
    "        return dfs(1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums) // 2\n",
    "        @ cache\n",
    "        def dfs(idx):\n",
    "            tmp = [0] * (2 * n)\n",
    "            for i in range(2 * n):\n",
    "                if (idx >> i) & 1:\n",
    "                    tmp[i] = nums[i]\n",
    "            ni = sum([1 for t in tmp if t > 0]) // 2\n",
    "            if ni == 0:\n",
    "                return 0\n",
    "            flag = max([math.gcd(tmp[i], tmp[j]) for i in range(2 * n) for j in range(i + 1, 2 * n) if tmp[i] >0 and tmp[j] > 0])\n",
    "            ans = 0\n",
    "            for i in range(2 * n):\n",
    "                if tmp[i] == 0:\n",
    "                    continue\n",
    "                for j in range(i + 1, 2 * n):\n",
    "                    if tmp[j] > 0:\n",
    "                        ans = max(ans, dfs(idx - (1 << i) - (1 << j)) + ni * math.gcd(tmp[i], tmp[j]))\n",
    "            return ans\n",
    "        return dfs(2 ** 14 - 1)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def fun(now, visit):\n",
    "            if now == n // 2:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                for j in range(i):\n",
    "                    if not visit & (1 << i) and not visit & (1 << j):\n",
    "                        res = max(res, gcd(nums[i], nums[j])*(now+1) + fun(now+1, visit | (1 << i) | (1 << j)))\n",
    "            return res\n",
    "        return fun(0, 0)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(state, idx):\n",
    "            if state == (1 << n) - 1:\n",
    "                return 0\n",
    "            score = -1\n",
    "            for i in range(n):\n",
    "                if (1 << i) & state == 0:\n",
    "                    for j in range(i + 1, n):\n",
    "                        if (1 << j) & state == 0:\n",
    "                            new_state = state\n",
    "                            new_state |= 1 << i\n",
    "                            new_state |= 1 << j\n",
    "\n",
    "                            score = max(score, idx * gcd(nums[i], nums[j]) + dp(new_state, idx + 1) )\n",
    "\n",
    "            return score\n",
    "        n = len(nums)\n",
    "        return dp(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        G = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                G[i][j] = gcd(nums[i], nums[j])\n",
    "        @cache\n",
    "        def dfs(c, mask):\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i == j: continue\n",
    "                    if mask >> i & 1 and mask >> j & 1:\n",
    "                        res = max(res, dfs(c + 1, mask ^ (1 << i) ^ (1 << j)) + c * G[i][j])\n",
    "            return res\n",
    "        return dfs(1, (1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(mask,k)->int:\n",
    "            if mask == 1 << n - 1:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1,n):\n",
    "                    if (mask >> i) & 1 == 0 and (mask >> j) & 1 == 0:\n",
    "                        mask ^= (1 << i)\n",
    "                        mask ^= (1 << j)\n",
    "                        res = max(res,k * gcd(nums[i],nums[j]) + dfs(mask,k + 1))\n",
    "                        mask ^= (1 << i)\n",
    "                        mask ^= (1 << j)\n",
    "            return res\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        t = (1<<n) - 1\n",
    "        # print(\"------\")\n",
    "        # print(bin(t))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state,cnt):\n",
    "            # print(bin(state),cnt)\n",
    "            if state == t:\n",
    "                return 0\n",
    "            ans = -inf\n",
    "            for i in range(n):\n",
    "                if state & (1<<i) == 0:\n",
    "                    for j in range(i+1,n):\n",
    "                        if state & (1<<j) == 0:\n",
    "                            ans = max(ans,cnt*gcd(nums[i],nums[j])+dfs(state | 1<<i | 1<<j, cnt+1))\n",
    "            return ans\n",
    "        return dfs(0,1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(mask,k)->int:\n",
    "            if mask == 1 << n - 1:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1,n):\n",
    "                    if (mask >> i) & 1 == 0 and (mask >> j) & 1 == 0:\n",
    "                        res = max(res,k * gcd(nums[i],nums[j]) + dfs(mask | (1 << i) | (1 << j),k + 1))\n",
    "\n",
    "            return res\n",
    "        return dfs(0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for j in range(n):\n",
    "                if mask >> j & 1:\n",
    "                    for k in range(j + 1,n):\n",
    "                        if mask >> k & 1:\n",
    "                            ans = max(ans,i*gcd(nums[j],nums[k]) + dfs(i + 1,mask ^ (1 << j)^(1 << k)))\n",
    "            return ans            \n",
    "\n",
    "        return dfs(1,(1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(state:int):\n",
    "            if state == 0:\n",
    "                return 0\n",
    "            t = 0\n",
    "            for i in range(n):\n",
    "                if (1<<i)&state == 0:\n",
    "                    t+=1\n",
    "            t //= 2\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if ((1<<i)&state) > 0:\n",
    "                    for j in range(i+1, n):\n",
    "                        if ((1<<j)&state) > 0:\n",
    "                            res = max(res, (t+1)*gcd(nums[i], nums[j])+f(state^(1<<i)^(1<<j)) )\n",
    "            return res\n",
    "        return f((1<<n)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def f(mask: int) -> int:\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            u = 0\n",
    "            for i in range(0, n):\n",
    "                for j in range(i + 1, n):\n",
    "                    if mask >> i & 1 and mask >> j & 1:\n",
    "                        u = max(u, f(mask ^ (1 << i | 1 << j)) + math.gcd(nums[i], nums[j]) * (1 + (n - mask.bit_count()) // 2))\n",
    "            ans += u\n",
    "            return ans\n",
    "\n",
    "        return f((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "        L = len(nums)\n",
    "        N = L // 2\n",
    "        # i: 第i次操作(从1开始)\n",
    "        # state: nums中元素的使用情况\n",
    "        @cache\n",
    "        def dfs(state):\n",
    "            bin(state)\n",
    "            i = state.bit_count()//2+1\n",
    "            if i > N: return 0\n",
    "            # 先获取nums目前可用的元素(下标)\n",
    "            usable = [j for j in range(L) if state >> j & 1 == 0]\n",
    "            return max(i * gcd(nums[a], nums[b]) + dfs(state | (1 << a) | (1 << b)) for a, b in combinations(usable, 2))\n",
    "        \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, nums: List[int]) -> int:\n",
    "\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        mp = {}\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                mp[(i, j)] = gcd(nums[i], nums[j])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(state, idx):\n",
    "            if state == (1 << n) - 1:\n",
    "                return 0\n",
    "            score = -1\n",
    "            for i in range(n):\n",
    "                if (1 << i) & state == 0:\n",
    "                    for j in range(i + 1, n):\n",
    "                        if (1 << j) & state == 0:\n",
    "                            new_state = state\n",
    "                            new_state |= 1 << i\n",
    "                            new_state |= 1 << j\n",
    "\n",
    "                            score = max(score, idx * mp[(i, j)] + dp(new_state, idx + 1) )\n",
    "\n",
    "            return score\n",
    "        n = len(nums)\n",
    "        return dp(0, 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
